import java.util.Arrays;
import java.util.Iterator;

/**
 * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数
 * 
 * @author Lenovo
 *
 */
public class 数组旋转 {
	public static void main(String[] args) {
		int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
		            //0  1  2  3  4   5  6
		            //5  6  7  1  2   3   4  
		// 7,2,3,4,5,6,7;
		// curr:7
		// 7,1,2,3,4,5,6
		// 7,1,2,3,4,5,6
		rorate(arr, 3);
		System.out.println(Arrays.toString(arr));

	}

	// 向右平移3位
	// 第一次： arr[length-1]

	/**
	 * 把数组向右平移k位
	 * 
	 * @param arr
	 * @param k
	 */
	static void rorate(int[] arr, int k) {
		// 平移1位。拿末尾元素和前面元素逐个交换1次，需要循环1次
		// 平移1位。k次拿末尾元素和前面元素逐个交换1次，需要循环k次
		for (int i = 0; i < k; i++) {
			int curr = arr[arr.length - 1];
//			for (int j = 0; j < arr.length; j++) {
//				int temp = arr[j];
//				arr[j] = arr[j+1];
//				arr[j+1] = temp;
//			}
			
			for (int j = arr.length-1; j > 0 ; j--) {
				int temp = arr[j];
				arr[j] = curr;
				curr = temp;
			}
		}
	}

	static void rorate1(int[] arr, int k) {
		reverse(arr, 0, arr.length - 1);
		reverse(arr, 0, k-1);
		reverse(arr, k, arr.length - 1);
	}

	static void reverse(int[] arr, int left, int right) {
		while (left < right) {
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
			left++;
			right--;

		}

	}
	
	/**
	 * 借助新数组来实现把旧数组的元素存到(i + k)%length
	 * @param arr
	 * @param k
	 * @return
	 */
	static int[] rorate2(int[] arr, int k) {
		int length = arr.length;
		int[] newArr = new int[length];
		for (int i = 0; i < length; i++) {
			newArr[(i+k)%length] = arr[i];
		}
		return newArr;
	}

}
